A bottleneck bandwidth is the lowest bandwidth of any link on a multi-hop path. This bandwidth poses a constraint on the path throughput. FIG. 1 illustrates a probe gap technique for estimating bandwidth on a directional path from the hosts 1 (Ra to Rb). Hosts 1 Ra and Rb are both fronted by encryption devices 5 (Ea and Eb). The encryption devices 5 are between a red (plaintext) and a black network (ciphertext) 3. The path between hosts 1 passes to a multi-hop path through m nodes 15 (N1, N2, Nm) in the black network 3. To estimate bandwidth, Ra sends one or more probe pairs 10, e.g., probe packets 1 and 2, back-to-back, to Rb. FIG. 1 illustrates an arrow in the forward direction to show the probe pair 10 being sent from Ra to Rb. These probe pairs propagate through the black network 3, with network conditions (including the link bandwidths on each hop, and congestion at each node) altering the gap between the probes 10. When the probe pairs 10 arrive at Rb, Rb infers a bandwidth estimate from the time gap between the packets in the probe pair 10, and sends the bandwidth estimate back to Ra via a separate message 20. The time gap in FIG. 1 is depicts as a space between probe packets 1 and 2. FIG. 1 illustrates an arrow in the reverse direction to show the bandwidth estimate being sent from Rb to Ra. Specifically, B=L2/(T2−T1), where B is the bottleneck bandwidth, L2 is the length of the second probe in bits, and T1 and T2 are the arrival times of the first and second probes, respectively.
However, the probe gap is subject to effects of packet queuing and cross traffic, including packets from other flows being inserted between the probe pair 10. If non-probe packets are queued between two probes making up a probe pair 10, the probe gap will no longer reflect the true link bandwidth, but will reflect the combined time for transmitting the second probe as well as the interspersed packet(s). This problem will cause the probe gap technique to under-estimate the bandwidth. If the probes remain back-to back, but become queued at a point downstream from the bandwidth bottleneck, then the resulting probe gap will reflect the bandwidth at the queuing point, not the bottleneck bandwidth. This effect could lead to a substantial over-estimation of the bottleneck bandwidth.
The addition of encryption (red/black) boundaries at network edges makes the task of bandwidth estimation even more difficult for hosts on the red (plaintext) side of the encryption boundary, e.g., Ea and Eb. From the standpoint of red-side hosts 1, the boundary hides many details of black-network operation, and prevents direct exchange of network state information via flows between hosts Ra and Rb or nodes 15 on opposite sides of the boundary. As a result, even if nodes N1-Nm within the black network 3 could accurately measure network bandwidth, these nodes 15 would not be able to communicate this information across the boundary to hosts 1 on the red side.